package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/symmetric-tree/">对称二叉树 [简单]</a>
 * 给定一个二叉树的根节点root，检查是否左右对称
 * 提示：
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 * 进阶：使用递归和迭代两种方式实现
 *
 * @author zhenzicheng
 * @date 2022-06-05 17:20
 */
public class SymmetricTree_101 {

  /**
   * 递归
   */
  // public boolean isSymmetric(TreeNode root) {
  //   return deepAccess(root.left, root.right);
  // }

  // public boolean deepAccess(TreeNode left, TreeNode right) {
  //   if (left == null && right == null) {
  //     return true;
  //   }
  //
  //   if (left == null || right == null) {
  //     return false;
  //   }
  //
  //   if (left.val != right.val) {
  //     return false;
  //   }
  //
  //   return deepAccess(left.left, right.right) && deepAccess(left.right, right.left);
  // }

  /**
   * 迭代
   */
  public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    TreeNode left = root.left, right = root.right;

    if (left == null && right == null) {
      return true;
    }
    q.offer(left);
    q.offer(right);

    while (!q.isEmpty()) {
      left = q.poll();
      right = q.poll();

      if (left == null && right == null) {
        continue;
      }

      if ((left == null || right == null) || (left.val != right.val)) {
        return false;
      }

      // 都不为空，并且上次的节点值也想同，将新的子节点存入队列
      q.offer(left.left);
      q.offer(right.right);

      q.offer(left.right);
      q.offer(right.left);
    }

    return true; // 都通过代表镜像对称
  }


}
